import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class LeetCode144 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );

        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;//记录当前节点
        TreeNode pop = null; // 记录上一个被访问的节点
        while (cur != null || !stack.isEmpty()) {
            //左子树为空是弹出
            if (cur != null) {
//                list.add(cur.val);
                stack.push(cur);//压入栈，为了记住回来的路
                cur = cur.left;
            } else {
                TreeNode peek = stack.peek();//栈顶元素
                if (peek.right == null || peek.right == pop) {//右子树处理完成
                    pop = stack.pop();//更新prev为当前访问的节点
                    list.add(pop.val);
                } else {
                    //否则，进入右边的分支
                    cur = peek.right;
                }
            }
        }
        System.out.println("回：" + list);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        //判断是否为空
        if (root == null) {
            return res;
        }
        //不为空递归
        res.add(root.val);
        res.addAll(preorderTraversal(root.left));
        res.addAll(preorderTraversal(root.right));
        return res;
    }
}
